\documentclass[11pt]{report}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{geometry} 
\usepackage{verbatim} 
\usepackage{amsmath,amsfonts,amssymb,amscd,amsthm,xspace}
\usepackage[ngerman]{babel}
\usepackage{amssymb}

\newtheorem{satz}{Satz}
\newtheorem{korollar}{Korollar}
\newtheorem{lemma}{Lemma}
\usepackage{multicol}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{algorithmic}
\usepackage{algorithm}

\usepackage{mathcomp}

% under and oversets
\newcommand{\Os}[2]{\overset{#1}{#2}}
\newcommand{\Us}[2]{\underset{#1}{#2}}
\newcommand{\OS}[2]{\Os{#1}{\overbrace{#2}}}
\newcommand{\US}[2]{\Us{#1}{\underbrace{#2}}}
% logic
\newcommand{\lfollow}{\rightarrow} % logical follow
\newcommand{\sfollow}{\Longrightarrow} % semantic follow

\geometry{a4paper, left=2cm,right=2cm,top=2cm,bottom=2cm}
\parindent0.0em
\title{{\Huge Höhere Algroithmik II} \\ \vspace{1cm} {\Small Vorlesung von Prof. Helmut Alt, FU Berlin, Sommersemester 2011}}
\author{Eine Mitschrift der Studierenden}
\date{\today}
\begin{document}
%\maketitle

\chapter{Algebraische und arithmetische Algorithmen}
\section{Das algebraische Berechnungsmodell}
Struktur: Körper (oder Ring) mit den Operationen $+$, $-$, $*$, $(/)$\\
Eingabe: endliche Folge von Zahlen\\
Ausgabe: endliche Folge von Zahlen\\
``Laufzeit'': Anzahl der Operationen als Funktion der Eingabelänge.\\
Verwendet werden Abfragen auf 0, Schleifen, Rekursionen etc.

\section{Matrizenmultiplikation}
Eingabe: Zwei $(n\times n)$-Matrizen über einem Ring
\[ A = \left( \begin{array}{ccc} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots &  \vdots \\ a_{n1} & \cdots & a_{nn} \end{array} \right) \text{ und } B = \left( \begin{array}{ccc} b_{11} & \cdots & b_{1n} \\ \vdots & \ddots &  \vdots \\ b_{n1} & \cdots & b_{nn} \end{array} \right)\]
Ausgabe: $(n\times n)$-Matrix 
\[C = \left( \begin{array}{ccc} c_{11} & \cdots & c_{1n} \\ \vdots & \ddots &  \vdots \\ c_{n1} & \cdots & c_{nn} \end{array}\right) \text{ mit } c_{ij} = \sum_{k=1}^n a_{ik} \cdot b_{kj} \, , 1 \leq i,j \leq n\]
Der naive Algorithmus nach dieser Formel benutzt drei verschachtelte Schleifen über $i$, $j$ und $k$. Das ergibt eine Laufzeit von $\Theta(n^3)$:\\
\renewcommand{\arraystretch}{1.5}
\begin{tabular}{ll}
$n^2\cdot n$ & Multiplikationen\\
$n^2\cdot (n-1)$ & Additionen\\
\hline
$2n^3-n^2$ & Operationen
\end{tabular}\\
Für $n=2$ sind es also 8 Multiplikationen und 4 Addidtionen. \textit{Geht es noch schneller}?

\subsection{Algorithmus von Strassen (1969)}
Der deutsche Mathematiker Volker Strassen die fand folgende Formel, um $(2\times 2)$-Matrizen zu multiplizieren:
\[A \cdot B = C = \left( \begin{array}{cc} c_{11} & c_{12} \\ c_{21} & c_{22} \end{array}\right) \text{ mit}\]
\begin{eqnarray*} 
c_{11} &=& m_1 + m_2 - m_4 + m_6\\
c_{12} &=& m_4 + m_5 \\
c_{21} &=& m_6 + m_7 \\
c_{22} &=& m_2 - m_3 + m_5 - m_7 \\
m_1 &=& (a_{12} - a_{22}) \cdot (b_{21} + b_{22})\\
m_2 &=& (a_{11} + a_{22}) \cdot (b_{11} + b_{22})\\
m_3 &=& (a_{11} - a_{21}) \cdot (b_{11} + b_{12})\\
m_4 &=& (a_{11} + a_{12}) \cdot b_{22}\\
m_5 &=& a_{11} \cdot (b_{12} - b_{22})\\
m_6 &=& a_{22} \cdot (b_{21} - b_{11})\\
m_7 &=& (a_{21} + a_{22}) \cdot b_{11}
 \end{eqnarray*}
wobei $a_{ij} b_{ij}$ wie zuvor die Elemente der Matrizen $A$ und $B$ bezeichnen.\\
\medskip

Diese Methode nutzt 7 Multiplikationen und 18 Additionen und lässt sich zu einem rekursiven Algorithmus zur Multiplikation quadratischer Matrizen beliebiger Größe erweitern. Dazu führt man die Matrizenmultiplikation zunächst auf den Fall für $(2\times 2)$-Matrizen zurück.\\
\medskip

Gegeben seien zwei Matrizen über einem Ring $R$: $A,B \in R^{n\times n}$ mit $n=2^k, k \in \mathbb{N}^+$ mit
\[A = \left( \begin{array}{c|c} A_{11} & A_{12} \\ \hline A_{21} & A_{22} \end{array}\right) \text{ und } B = \left( \begin{array}{c|c} B_{11} & B_{12} \\ \hline B_{21} & B_{22} \end{array}\right)\]
Hier sind $A_{ij}, B_{ij} \in R^{\frac{n}{2}\times \frac{n}{2}} \text{ für } 1 \leq i,j \leq 2$. 
Nun gilt
\[ A\cdot B = \left( \begin{array}{c|c} A_{11} B_{11} + A_{12} B_{21} & A_{11} B_{12} + A_{12} B_{22} \\ \hline  A_{21} B_{11} + A_{22} B_{21} & A_{21} B_{12} + A_{22} B_{22} \end{array}\right) \]
Damit ist die Multiplikation von $(n\times n)$-Matrizen auf 7 Multiplikationen und 18 Additionen von $(\frac{n}{2}\times \frac{n}{2})$-Matrizen zurückgeführt. Als Rekursionsanker wählen wir $(1\times 1)$-Matrizen (was Elementen aus $R$ entspricht).\\

\textit{Das Verfahren lässt sich auch für quadratische Matrizen beliebiger Größe anwenden, indem man die Matrix bis zur nächsten Zweierpotenz mit Nullen auffüllt. Die Dimension der Matrix kann sich dadurch höchstens verdoppeln.}
\medskip

Die Laufzeit des Algorithmus ist:
\begin{eqnarray*}
M(1) &=& 1\\
M(n) &=& 7 M \left(\frac{n}{2}\right) + 18 \left(\frac{n}{2}\right)^2 \\
     &=& 7 M \left(\frac{n}{2}\right) + \frac{9}{2} n^2 \\
     &=& 7\cdot (7 M(\frac{n}{4}) + \frac{9}{2}\cdot \left(\frac{n}{2}\right)^2 ) + \frac{9}{2} n^2 \\
     &=& ...\\
     &=& 7^k M \left(\frac{n}{2^k}\right) + \frac{9}{2}\cdot \left( n^2 + 7\cdot \left(\frac{n}{2}\right)^2 + ... + 7^{k-1} \cdot \left(\frac{n}{2^{k-1}}\right)^2 \right)\\
     &=& n^{log_2\,7} + \frac{9}{2}n^2\cdot \frac{\left(\frac{7}{4}\right)^{log_2\,n} - 1}{\frac{7}{4} -1}  \phantom{abstandhier} \left[ \left(\frac{1}{4}\right)^{log_2\,n} \textit{ kürzt sich mit } n^2 \right] \\
     &=& 7n^{log_2\,7} - 6n^2 \quad \Rightarrow \quad \Theta(n^{log_2\,7})
\end{eqnarray*}
Durch den kleineren Exponenten von $log_2\,7 = 2,807.. < 3$ ist der Strassen-Algorithmus asymptotisch schneller als der naive Algorithmus ist. \textit{Aber geht es (asymptotisch) noch schneller}?

\subsection{Ausblick}
Falls für ein  $k \in \mathbb{N}$ das Produkt zweier $(k\times k)$-Matrizen mit $p$ Multiplikationen berechenbar ist, so ist allgemein das Produkt zweier $(n\times n)$-Matrizen in $\mathcal{O}(n^{log_k\,p})$ Operationen berechenbar.\\

Strassen fand das Paar $k=2, p=7$. Seitdem gab es weitere Arbeiten auf diesem Gebiet, die die Laufzeit noch weiter reduzieren konnten auf $\Theta(n^x)$:\\

\begin{tabular}{|c|c|c|c|}
\hline
Victor Pan & 1978 & $k=70, p=143640$ & $x= 2,795..$ \\
\hline
Bini, Capovani, Lotti, Romani & 1979 & & $x= 2,779..$\\
\hline
Schönhage & 1979 & & $x= 2,55..$\\
\hline
Pan, Winogard & 1980 & & $x= 2,54..$\\
\hline
Coppersmith, Winogard & 1980 & & $x= 2,376..$\\
\hline
\end{tabular}

\section{Inversion und Determinante von Matrizen}
Wir betrachten $(n\times n)$-Matrizen über einem Körper $K$. Gegeben ist die Matrix $A$ über $K$ und gesucht ist $A^{-1}$, falls $A$ regulär ist. Die Laufzeit bezeichnet wieder die Anzahl der Körperoperationen $+,-,*,/$.\\

Mit dem klassischen Gauss-Eliminationsverfahren lässt sich die Inverse berechnen, indem man die Matrix $A$ mit Zeilenoperationen in die Einheitsmatrix überführt und die selben Operationen auch auf eine Einheitsmatrix anwedet:
\[ \left( \begin{array}{c|c} A & I_n\end{array}\right) \quad \Rightarrow \quad  \left( \begin{array}{c|c} I_n & A^{-1} \end{array}\right)  \]
Die Elimination eines Elementes der Matrix benötigt eine Zeilenoperation, welche in $\mathcal{O}(n)$ arbeitet. Insgesamt ergibt sich also eine Laufzeit von $\Theta(n^3)$.\\
\medskip

\textbf{Rückführung der Inversion auf Matrizenmultiplikation:}\\
Sei wieder $A \in K^{n \times n}$ mit $n = 2^k, k \in \mathbb{N^+}$. Unter der Voraussetzung, dass $A_{11}$ regulär ist, gilt folgende Zerlegung:
\[A = \underset{X}{\underbrace{ \left( \begin{array}{cc} I_\frac{n}{2} & 0_\frac{n}{2} \\ A_{21} A^{-1}_{11} & I_\frac{n}{2} \end{array}\right)} }   \underset{Y}{ \underbrace{\left( \begin{array}{cc} A_{11} & 0_\frac{n}{2} \\ 0_\frac{n}{2} & D \end{array}\right)} }  \underset{Z}{\underbrace{ \left( \begin{array}{cc} I_\frac{n}{2} & A^{-1}_{11} A_{12} \\ 0_\frac{n}{2} & I_\frac{n}{2} \end{array}\right)} } \]
Dabei bezeichnen $A_{ij}, 1\leq i,j \leq 2$ die $(\frac{n}{2}\times \frac{n}{2})$-Blockmatrizen aus $A$, $I_\frac{n}{2}$ die Einheitsmatrix der Größe $\frac{n}{2}$ und $0_\frac{n}{2}$ die Nullmatrix der Größe $\frac{n}{2}$. Die Matrix D berechnet sich aus
\begin{eqnarray*} D &=& A_{22} - A_{21}  A^{-1}_{11}  A_{12} \end{eqnarray*}
Die Matrizen $X$ und $Z$ sind regulär, weil ihre Determinante 1 ist (Dreiecksform). Wenn sowohl $A_{11}$ als auch $D$ regulär sind, dann ist $Y$ ebenfalls regulär und es gilt:
\[A^{-1}= \underset{Z^{-1}}{\underbrace{ \left( \begin{array}{cc} I_\frac{n}{2} & - A^{-1}_{11} A_{12}  \\ 0_\frac{n}{2} & I_\frac{n}{2} \end{array}\right)} }   \underset{Y^{-1}}{ \underbrace{\left( \begin{array}{cc} A^{-1}_{11} & 0_\frac{n}{2} \\ 0_\frac{n}{2} & D^{-1} \end{array}\right)} }  \underset{X^{-1}}{\underbrace{ \left( \begin{array}{cc} I_\frac{n}{2} & 0_\frac{n}{2} \\ - A_{21} A^{-1}_{11} & I_\frac{n}{2} \end{array}\right)} }\]
Das liefert einen rekursiven Algorithmus zum Invertieren einer $(n\times n)$-Matrix.
\medskip

Die Determinante von $A$ lässt sich ebenfalls auf diese Art zurückführen:
\begin{eqnarray*}
\text{det}\,A &=& \text{det}\,X \cdot \text{det}\,Y \cdot \text{det}\,Z \\ &=& 1 \cdot \text{det}\,Y \cdot 1 \\ &=& \text{det}\,A_{11} \cdot \text{det}\,D
\end{eqnarray*}
\medskip

Bisher wird immer vorausgesetzt, dass $A_{11}$ regulär ist. Falls dies nicht gewährleistet ist, lässt sich zumindest in den Körpern $\mathbb{R}$ und $\mathbb{Q}$ folgender Trick nutzen ($A^T$ = A transponiert):
\[A^{-1} = (A^T\cdot A)^{-1} \cdot A^T \]
Die Matrix $A^T\cdot A$ ist positiv definit und symmetrisch.
\bigskip

\textit{to be continued ...}


%%
%% Beginn Vorlesung 18.04.2011 


\section{Multiplikation Boolscher Matrizen (Fortsetzung 18.04.)}
Da die Einträge $\hat{c}_{ij}$ $\leq$ $n$ sind, können wir statt über $\mathbb{Z}$ auch über $\mathbb{Z}_{n+1}$ rechnen.
$\mathbb{Z}_{n+1}$ ist ein Ring, d.h. die schnelle Matrizen Multiplikation ist anwendbar.\\
($\hat{c}_{ij}$ sind die Ergebnisse der Multiplikation)\\
\\
jetzt noch:\\
\textbf{ Anzahl der Bitoperationen für eine Multiplikation/Addition/Subtraktion auf $\mathbb{Z}_{n+1}$}\\
\\
(Die Zahlen werden binär dargestellt mit $\lceil \log (n+1) \rceil$ Bits.)\\
\\
Addition und Subtraktion von zwei $k$-Bit-Zahlen braucht $O(k)$ Bitoperationen (nach der Schulmethode und der Implementierung im Schaltkreis).\\
Für die Multiplikation werden $O(k^2)$ Bitoperationen benötigt.
\begin{multicols}{2}
Beispiel für die Addition:\\
\\
$\begin{array}{cccccc}
 & & 1 & 0 & 1 & 1 \\
 + & & 1 & 0 & 0 & 1 \\
\hline
& 1 & 0 & 1 & 0 & 0 \\
 \end{array}
$
\\
\\
\columnbreak
\\
Beispiel für die Multiplikation:\\
\\
$\begin{array}{ccccccccc}
1 & 0 & 1 & 1 & \cdot & 1 & 0 & 0 & 1\\
\hline
 & & & & & 1 &  0 & 1 & 1 \\
 & & 1 & 0 & 1 & 1 & & & \\
\hline
& & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\
 \end{array}
$
\end{multicols}

\begin{satz}$\\{}$
Falls die Matrizenmultiplikation über einem Ring in $M(m)$ arithmetischen Operationen möglich
ist und Multiplikation/Addition/Subtraktion von k-Bitzahlen in $m(k)$ Bitoperationen, so kann man mit
 $O(M(n) \cdot m (\lceil \log (n+1)  \rceil ))$ Bitoperationen boolsche $ n \times n$-Matrizen multiplizieren.
\end{satz}


zum Beispiel:\\
\[
\left.
\begin{array}{ll}
M(n) = O(n^{2,376\dots})\\
m(k) = O(k^2)\\
\end{array} \right\}
{O(n^{2,376\dots} \cdot \log ^2 (n)) = O(n^{2,377})}
\]
 (boolsche Matrizenmultiplikation)
\\
\\
\subsection{Transitiver Abschluss Boolscher Matrizen}
 gegeben: \\
\begin{tabular}{rl}
Boolsche $n \times n$-Matrix $A$ & $\hat{=}$ gerichteter Graph $G_A$ mit $n$ Knoten (o.B.d.A. $V=\{1,\dots,n\}$) \\
& $\hat{=}$ binäre Relation $R_A$ auf einer $n$-elementigen Menge\\
\end{tabular}\\
\\
\\
Wir wollen den reflexiven und den transitiven Abschluss dieser Relation (Matrix $A^{*}$) berechnen.\\
\begin{eqnarray*}
A^{*} := I \vee A \vee A^2 \vee A^3 \vee \dots = \bigvee\limits^{\infty}_{i=0} A^i
\end{eqnarray*}
(komponentenweises Oder)\\
\\
$(A^*)_{ij} = 1 \Leftrightarrow$ in $G_A$ existiert ein Weg von $i$ nach $j$, denn:\\
\\
$(A^*)_{ij} = 1 \Leftrightarrow$ in $G_A$ existiert ein Weg der Länge $k$ von $i$ nach $j$\\
\\
\\
Beweis durch Induktion:\\
\\
$\left.
\includegraphics[scale=0.15]{Skizze1}
\right.$
 (es existiert ein Weg von $i$ nach $r$ mit der Länge $k-1$)\\
\\
\\
$(A^{k-1})_{ir} = 1$ $a_{rj} = 1$ und $(A^k)_{ij} = \bigvee\limits^n_{i=0} (A^{k-1})_{ir}$ $a_{ij}$
)\\
\\
\\
\textbf{Zusammenhang: transitiver Abschluss $\leftrightarrow$ Multiplikation:}\\
\begin{satz}$\\{}$
\textbf{a)}
Falls die Multiplikation boolscher Matrizen mit $M(n)$ boolschen Operationen möglich ist,
dann ist der transitiver Abschluss in $O(M(n))$ möglich.\\
(Vorraussetzung: $4 \cdot M(^n/_2) \leq M(n)$, $M(2n) \leq c$ für ein $c > 0$)\\
\\
\textbf{b)}
transitiver Abschluss in $A(n)$ möglich, denn Multiplikation in $A(3n)$
\end{satz}
$\\{}$
\begin{proof}
(Annahme $n$ ist eine Zweierpotenz)\\
\\
\textbf{a)}
wenn $A= \left(
\begin{array}{c|c}
B & C \\
\hline
D & E \\
\end{array}
\right)$
\hspace{2em}
dann ist $A^* = 
	    \left(\begin{array}{c|c}
            \underbrace{(B \vee C E^* D)^*}\limits_{:= F}&	F C E^* \\
	    \hline
	    E^* D F		&	E^* \vee E^* D F C E^* \\
            \end{array}\right)
$\\
\\
\\
Die transitive Hülle von $n \times n$-Matrix kann auf 2 transitive Hüllen von
 $^n/_2 \times {}^n/_2$ -Matrizen ($E^*$ und $F$) und 6 Multiplikation und 2 Additionen zurückgeführt werden.\\
\newpage
$A(n) = 2 A(^n /_2) + 6 M(^n/_2) + O(n^2)$ für $n \geq 2$\\
$A(1) = 0$\\
\\
 $\begin{array}{ll}\textrm{also gilt:} & A(n) = 2 A(^n /_2) + O(M(n))\\
& \Rightarrow A(n) = O(M(n))\end{array}$ (wie bei Inversion auflösen)\\
\\
\\
Beispiel für die Graphendarstellung von $G_A$:\\
\begin{center}
 $\left.
\begin{array}{l}
1\dots ^n/_2 \hspace{5em} ^n/_2 +1 \dots n \\  
\includegraphics[scale=0.25]{Skizze2}\\
\end{array}
\right.$
\end{center}
Pfade innerhalb der linken Seite werden durch die Einträge in $B$ repräsentiert.\\
Pfade innerhalb der rechten Seite werden durch die Einträge in $E$ repräsentiert.\\
Pfade von der linken zur rechten Seite werden durch die Einträge in $C$ repräsentiert.\\
Pfade von der rechten zur linken Seite werden durch die Einträge in $D$ repräsentiert.\\
\\
Bisherige Methode: Für jeden Knoten in $G_A$ wird eine Breitensuche durchgeführt.\\
 $O(n(n+m))$\\
\\
(Alternativ kann bei dünn besetzten Matrizen Multiplikation effizient durchgeführt werden.)\\
\\
\\
\textbf{b)}
Übung


\end{proof}



%\rule{\textwidth}{0.4pt} \\

\textbf{Was kann man noch auf Matrizenmultiplikation reduzieren?}\\
\\
Analyse kontextfreier Sprachen geht in $O(M(n))$. (Dazu wird ein angepasster CYK-Algorithmus verwendet.)\\
$M :=$ Komplexität der boolschen Matrizenmultiplikation\\


\section{Polynommultiplikation, diskrete Fourier-Transformation}
gegeben:\\
\begin{tabular}{l}
Sei $K$ ein K\"orper. Wir betrachten den Polynomring $K[x]$, der die Polynome \"uber $K$ in der Variablen $x$ enth\"alt.
\end{tabular}\\
\\
Polynome $P(x) = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \dots + a_n \cdot x^n$ mit
$n \geq 0,  a_0,\dots,a_n$ $\epsilon$ $K$
werden durch einen Vektor der Koeffizienten $(a_0,\dots,a_n)$ $\epsilon$ $K^{n+1}$  repräsentiert.\\
\\
Die Addition von Polynomen wird komponentenweise durchgeführt.\\
\\
Für die Multiplikation von Polynomen gilt:\\
$(a_0 + a_1 \cdot x + \dots + a_n \cdot x^n) \cdot (b_0 + b_1 \cdot x + \dots + b_n \cdot x^n)
 = c_0 + c_1 \cdot x + \dots + c_{2n} \cdot x^{2n}$\\
\\
mit $\left\{ \begin{array}{ll}
c_i = \sum\limits_{j=0}^{i} a_j b_{i-j}		&	$für $ i \leq n \\
c_i = \sum\limits_{j=i-n}^{n} a_j b_{i-j}	&	$für $ i > n 
\end{array} \right.\hspace*{1.5em} i = 0,\dots , 2n
$\\
\\
\\
$(c_0,\dots,c_{2n})$ heißt \underbar{Faltung} (\underbar{Konvolution}) von $(a_0,\dots,a_n)\otimes(b_0,\dots,b_n)$.\\
\\
\\
Wie viele Operationen (über $K$) sind nötig, um die Faltung (d.h. die Polynommultiplikation) zu berechnen?\\
\\
Direkt aus der Definition folgt: $2i+1$ Operationen für $i \leq n$\\
\\
$2(n-i)+1$ Operationen für $i = n+1,\dots , 2n$\\
\\
$\sum\limits_{i=0}^{n} 2i+1 + \sum\limits_{i = n+1}^{2n} 2(i-n)+1 = O(n^2)$


%%
%% Beginn Vorlesung 02.05.2011

\subsection{FFT ausf\"uhrlich}
\textbf{Geg:} Vektor $a = (a_0, ... , a_n) \in K^{n+1}$ K\"orper K, der eine primitive $(n+1)$-te Einheitswurzel $\omega$ besitzt. oBdA: $(n+1)$ ist eine Zweierpotenz.
\\
\\
\begin{algorithm}
\caption{FFT(a,n,$\omega$)}
\begin{algorithmic}[1]
\IF{$n=0$}
	\STATE return (a)
\ELSE
	\STATE $ag:=(a_0, a_2, ... a_{n-1})$
	\STATE $au:=(a_1, a_3, ... a_n)$
	\STATE $u:=FFT(ag,\frac{n-1}{2}, \omega^2)$ 
	\STATE $v:=FFT(au,\frac{n-1}{2}, \omega^2)$
	\STATE $w:=1$
	  \FOR{$i=0 \to \frac{n-1}{2}$}
	\STATE $y_i := u_i + w\cdot v_i$
	\STATE $y_{\frac{n+1}{2}+i} := u_i - w\cdot v_i$
	\STATE $w := \omega \cdot w$
	\ENDFOR
	\RETURN $(y_0, ... , y_n)$
\ENDIF
\end{algorithmic}
\end{algorithm}

\textbf{Erkl\"arung der Zeilen 8 - 15:} \\
f\"ur $i = 0, ... , \frac{n-1}{2}:$ \\
$w$ durchl\"auft $1, \omega, \omega^2, ... , \omega^{\frac{n-1}{2}}$ \\
$y_i$ soll sein: $\underbrace{p_1(\omega^{2i})}_{u_i} + \underbrace{\omega^i}_{w} \cdot \underbrace{p_2(\omega^{2i})}_{v_i} $ \\
f\"ur $i = \frac{n-1}{2}+1, ... ,n:$ \\
Wie sieht hier $\omega^{2i}$ aus? \\
$\begin{array}{ccccccccc}
2i 				& = & n + 1 & , & n + 3 & , & n + 5 & , & ... \\
\omega^{2i} & = & \omega^{(n+1)} & , & \omega^{(n+1) + 2} & , & \omega^{(n+1) + 4} & , & ... \\
\omega^{2i} & = & \omega^{2i-(n+1)} &  &  &  &  &  &  \\
\end{array}$ \\
Es werden hier die Werte von $p_1$ an diesen Stellen genommen. \\
$\omega^i$ f\"ur $i=\frac{n-1}{2}+1, ... , n$ ist gleich: \\
$\omega^{\frac{n+1}{2}+j}$ f\"ur $j=0, ... , \frac{n+1}{2}$ \\
$\omega^{\frac{n+1}{2}} = -1$ damit ist $\omega^{\frac{n+1}{2}+j} = -\omega^j$ \\
\textbf{Genaue Rekursionsgleichung:} \\
\begin{eqnarray*}
T(n+1) & = & 2 T(\frac{n+1}{2}) + \underbrace{3 \cdot \frac{n+1}{2}}_{ \textrm{K\"orperoperationen in Zeilen 8-14}} \\
T(n+1) & = & \frac{3}{2}(n+1) \cdot \log(n+1)
\end {eqnarray*}
\\
\\
F\"ur die Faltung (Konvolution, Polynommultiplikation) haben wir folgenden
\begin{satz}
\label{faltungssatz}
 \textbf{\textrm{\upshape{(Faltungssatz)}}} Seien $a,b \in K^{n+1}$ Vektoren, $K$ K\"orper mit primitiver (n+1)-ter Einheitswurzel, dann  gilt
  \begin{equation*}
   a \otimes b = DFT^{-1}(DFT(a) \cdot DFT(b))
  \end{equation*}
wobei $a \otimes b \in K^{2n+1}$ die Koeffizienten des Polynomproduktes darstellt, $a,b$ die Dimension $2n$ haben (werden mit $0$ aufgef\"ullt) und $\cdot$ f\"ur die komponentenweise Multiplikation steht.
\end{satz}

\begin{korollar}
 Die Multiplikation von Polynomen von Grad $n$ mit Koeffizienten aus $K$ (Eigenschaften wie in Satz \ref{faltungssatz}) ist m\"oglich mit $O(n\log n)$ Operationen \"uber dem K\"orper $K$.
\end{korollar}
Denn die Operationen in der Formel in Satz \ref{faltungssatz} ben\"otigen folgende Laufzeiten:
\newline
\begin{center}
 \begin{tabular}{|c p{10cm}|}
\hline
$DFT(a)$ & \multirow{2}{*}{in $O(n\log n)$ mit FFT m\"oglich} \\
$DFT(b)$ &   \\
\hline
$\cdot$ & geht in $O(n)$ Zeit \\
\hline
$DFT^{-1}$ & auch in $O(n \log n)$ m\"oglich, da die zugeh\"orige inverse Matrix 
$
\frac{1}{n+1}
\begin{pmatrix} 
1 & 1 & \cdots & 1 \\
1 & \omega^{-1} & \cdots & \omega^{-n} \\
\vdots & \vdots & \ddots & \vdots \\
1 & \omega^{n} & \cdots & \omega^{n^{2}} \\
\end{pmatrix}
$
ist.
\newline
\textrightarrow FFT unter Benutzung von $\omega^{-1}$ m\"oglich. Ergebnis muss mit $\underbrace{\frac{1}{n+1} \textrm{multipliziert\ }}_{O(n) \textrm{Zeit}}$      werden.
\\
\hline
\end{tabular} 
\end{center}

\subsection{Bedeutung der Fourier-Transformation}
Darstellung einer Funktion mit Hilfe der Einheitswurzeln $1,e^{i\cdot \frac{2\pi}{N}}, e^{i\cdot2\frac{2\pi}{N}},\dots, e^{i\cdot(N-1)\frac{2\pi}{N}}$. Dabei gilt 
\begin{equation*}
 e^{i \cdot k\frac{2\pi}{N}} = \cos(k\frac{2\pi}{N}) + \sin(k\frac{2\pi}{N}) = \omega^{k}
\end{equation*}
FFT gibt die Darstellung einer Funktion mit Hilfe von $\sin$ und $\cos$ verschiedener Frequenzen an. Die Koeffizienten sagen dabei aus wie stark die Frequenzen vertreten sind. Das Ergebnis der Fouriertransformation hei\ss t auch Spektrum.
\\
\begin{center}
\includegraphics[scale=1.00]{Frequenz2}\\
\end{center}

\textbf{Anwendungsgebiete:}
\begin{itemize}
\item Wirtschaftwissenschaften: Untersuchung von Preisschwankungen
\item Bild- und Signalverarbeitung: Hier werden durch Anwendung der Fourier-Transformation mit der Sinc-Funktion $\left(\operatorname{sinc}(x)= \frac{\sin(x)}{x}\right)$ Filter f\"ur die Rauschunterdr\"uckung erstellt. Es wird dabei in Hoch- und Tiefpassfiter unterschieden.
\end{itemize}

%%
%% Missing: Vorlesung 06.05.2011


%%
%% Beginn Vorlesung 09.05.2011
\subsection{Verbesserter Algorithmus zur Multiplikation von Bin\"arzahlen}
\textbf{Eingabe: } Bin\"arzahlen $a$, $b$ mit je $N$ Bits. \\
\textbf{Algortihmus: } \\
Falls $N=1$: \\
   gib $(a\wedge b)$ aus \\
Sonst: \\
\begin{enumerate}
	\item Teile $a$ und $b$ in $r + 1$ St\"ucke der Gr\"o\ss e $n$: \\
	$a_0, ... , a_r , b_0 , ... , b_r \in \left\{ 0, 1, ... , 2^n -1 \right\}$
	\item Betrachte Polynome $p(x) = \sum\limits_{i=0}^r a_i x^i , q(x)=\sum\limits_{i=0}^r b_i x^i$ und werte sie an den Stellen $ 1, 0 , ... , 2r$ aus 
	\item Berechne rekursiv die Produkte: \\
		\begin{eqnarray*}
		p_0\cdot q_0 & =: & w(0) \\
		\vdots & & \vdots \\
		p_{2r} \cdot q_{2r} & =: & w(2r)
		\end {eqnarray*}
		$w$ ist das Produktpolynom von $p$ und $q$
	\item Berechne durch Interpolation die Koeffizienten \\
	$c_0 , ... , c_{2r}$
	\item Berechne $w(2^n)$ , das ist also $a\cdot b$
\end{enumerate}
\textbf{Kostenanalyse: } \\
Schritt 2:\\
Die Auswertung der Polynome entspricht der Multiplikation mit der Matrix $A$: \\
\\
$\underbrace{\begin{pmatrix}
1 			& 	0 	& 	0 		& \cdots 	& 0 		\\
1 			& 	1 	& 	1 		& \cdots	& 1 		\\
1				&		2		&		4			& \cdots	& 2^{r} \\
\vdots	&\vdots	& \vdots	& \ddots	& \vdots\\
1				& 2r		& (2r)^2	& \cdots	& (2r)^r
\end{pmatrix}}_{A}
\cdot
\begin{pmatrix}
a_0 \\
a_1 \\
\vdots\\
\vdots\\
a_r
\end{pmatrix}
=
\begin{pmatrix}
p(0) \\
p(1) \\
\vdots\\
\vdots\\
p(2r)
\end{pmatrix}
$ \\
Produkt einer Zeile $\times$
$\begin{pmatrix}
p(0) \\
\vdots\\
p(2r)
\end{pmatrix} = \underbrace{1}_{konstant}\cdot a_0 + \underbrace{(2i)}_{konstant}\cdot a_1 + ... + \underbrace{(2i)^r }_{konstant} \cdot a_r$ \\
$a_0, ... , a_r$ haben je $n$ Bit. Eine Multiplikation einer Konstanten mit einer Zahl aus $a_0, ... , a_r$ kostet somit $O(n)$ Bitoperationen. Alle Multiplikationen insgesamt kosten immernoch $O(n)$ Bitoperationen.\\
Nimmt man nun die konstant vielen Additionen von $O(n)$-Bit-Zahlen hinzu, so bewegt man sich immer noch im Bereich von $O(n)$-Bit-Operationen. \\
Insgesammt m\"ussen $r$ Zeilen berechnet werden $\rightarrow O(n)$. Diese Operationen m\"ussen analog f\"ur $b$ durchgef\"uhrt werden. \\
Insgesamt erhalten wir f\"ur Schritt 2 $O(n)$ Operationen. \\
\\
Schritt 3:\\
$(2r+1)\cdot T(\frac{N}{r+1}) $ Operationen \\
\\
Schritt 4: \\
Die Multiplikation von 
$\begin{pmatrix}
w(0) \\
\vdots\\
w(2r)
\end{pmatrix}$
mit $A^{-1}$ geht mit $O(n)$ Operationen (siehe Schritt 2).\\
\\
Schritt 5: \\
$c_0, ... , c_{2n}$ sind die Koeffizienten von $w$. \\
Berechne $c_0 + c_1 \cdot 2^n + ... + c_{2r} \cdot 2^{2n \cdot 2r}$\\
Schema aufadieren: $O(n)$ \\
\\
Kosten insgesamt: \\
\begin{eqnarray*}
T(1) & = & 1 \\
T(N) & = & (2r + 1) \cdot T\left( \frac{N}{r+1} \right) + \underbrace{c \cdot \frac{N}{r+1}}_{O(n)} \\
T(N) & = & (2r + 1) \left( (2r+1) \cdot T\left( \frac{N}{(r+1)^2} \right) + c \cdot \frac{N}{(r+1)^2} \right) + c \cdot \frac{N}{r+1} \\
	& \vdots & \\
T(N) & = & (2r + 1)^k \cdot T\left( \frac{N}{(r+1)^k} \right) + cN \cdot \left( \frac{(2r +1)^{k-1}}{(r+1)^k} + ... + \frac{(2r +1)^0}{r+1} \right) \\
\end{eqnarray*}
Setze $k = \log_{r+1}N$: \\
\begin{eqnarray*}
T(N) & \leq & (2r + 1)^{\log_{r+1}N} + cN \cdot \frac{1}{r+1} \cdot \sum\limits_{j=0}^{k-1} 2^j \text{   (geom. Reihe, abgesch\"atzt)} \\
     & \leq & N^{\log_{r+1}(2r + 1)} + \underbrace{cN \cdot \frac{1}{r+1} \cdot 2^{\log_{r+1}N}}_{= \frac{cN}{r+1}^{\left( 1 + \log_{r+1}2 \right)} }
\end{eqnarray*}
F\"ur $r\rightarrow \infty $: 
\begin{eqnarray*}
\log_{r+1} (2r+1) \leq \log_{r+1}(2r+2) & = & 1 + \log_{r+1} 2
\end{eqnarray*}
also: 
\begin{eqnarray*}
T(N) & = & O\left( N^{1+\log_{r+1} 2} \right) \\
\log_{r+1} 2 & = & \frac{log_2 2}{log_2 (r+1)} \rightarrow 0  \text{ f\"ur }  r \rightarrow \infty 
\end{eqnarray*}
\\
F\"ur jedes $\epsilon > 0$ existiert ein $r\in N$, so dass $\epsilon > log_{r+1}2$. Damit haben wir einen Algorithmus zur Zahlenmultipliaktion mit den Kosten $O\left( N^{1+\epsilon} \right) $ f\"ur jedes feste $\epsilon > 0$. \\
\\
Noch besser: \\
$O\left( n\log n \cdot \log \log n \right)$ - Sch\"onhagen / Strassen 1971 \\
$O\left( n\log n \cdot 2^{O(\log^*n)} \right)$ - F\"urer 2009 \\
\\
Ist das wirklich schneller? \\
\begin{eqnarray*}
2^{c(\log^*n)} & ? & \log \log n \\
\text{log bilden:} \ \ \  c \log^*n & ? & \log \log \log n \\
							& \leq & \text{f\"ur hinreichend gro\ss es n}
\end{eqnarray*}

\subsection{Verbesserter Algorithmus zur Division von Bin\"arzahlen}
Schulmethode: $O(n^2)$ \\
Konvention: Bei der Eingabe von $n$-Bit-Zahlen soll das Ergebnis bis auf einen Fehler von $2^{-n}$ genau berechnet werden. \\
\\
\textbf{Zur\"uckf\"uhren der Division auf die Multiplikation:} \\
Idee: Um $\frac{a}{b}$ zu berechnen, berechne $\frac{1}{a}$ approximativ und multipliziere mit $b$ Die Berechnung von $\frac{1}{a}$ erfolgt durch Newton-Iteration. \\
\textbf{Exkurs: Newton-Iteration:}\\
Die Newton-Iteration ist ein Verfahren zum Bestimmen von Nullstellen einer Funktion.
\begin{figure}
	\centering
		\includegraphics[scale=0.5]{Newton-Iteration}
	\label{fig:Newton-Iteration}
\end{figure}
Konstruiere die Tangente durch $(x_i, f(x_i))$ mit der Steigung $f'(x_i)$ (siehe Abbildung). Daraus ergibt sich: \\
$x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}$ \\
\\
Bei richtigem Startwert hat die Newton-Iteration "Quadratische Konvergenz", d.h. sei $\epsilon_i$ der Fehler $\epsilon_i = \left| x^* - x_i \right|$, dann gilt: $\epsilon_{i+1} \leq c \cdot \epsilon_i^2$. \\
D.h. um einen Fehler $\leq 2$ zu bekommen sind $O(\log n)$ Schritte der Newton-Iteration n\"otig. 
\hrule 
\  
\newline
Zum Berechnen von $\frac{1}{a}$ kann die Newton Iteration auf folgende Funktion angewandt werden:
\begin{equation*}
 f(x)  =  \frac{1}{x} -a
\end{equation*}
Die Iterationsvorschrift ist dabei:
\begin{equation*}
 x_{i+1} =  x_i - \frac{f(x_i)}{f^{'}(x_i)} = x_i - \frac{\frac{1}{x} -a}{-\frac{1}{x_i^{2}}} = \US{\textrm{benutzt nur Multiplikationen}}{2x_i - ax_i^2}
\end{equation*}
Beim Rechnen mit $n$-Bit Zahlen werden $O(\log n)$ Schritte ben\"otigt, wobei jeder Schritt mit $O(M(n))$ Operationen durchf\"uhrbar ist und $M(n)$ f\"ur die Kosten einer Multiplikation steht. Die Gesammtkosten f\"ur die Berechnung von $\frac{1}{a}$ und damit $\frac{b}{a}$ sind $O(M(n)\cdot\log n)$. 

Neues Ziel: Faktor $\log n$ loswerden.
Da der Fehler im $k$-ten Schritt $O(2^{-2^{i}})$ ist, kann man im k-ten Schritt mit $2^k$ Bits Genauigkeit rechnen. 
\newline
$\Rightarrow$ Statt $M(n) \cdot \log n$:
\begin{equation*}
\begin{split}
 	& M(1) + M(2) + M(4) + \dots + M(2^{\log n}) \\
 = 	& M\US{2^{\log n}}{(n)} + M(\frac{n}{2}) + M(\frac{n}{4}) \cdots M(\frac{n}{n}) \\
 = 	&\sum\limits_{i=0}^{\log n} M \left( \frac{n}{2^i} \right) \\
 \leq 	& M(n) \sum\limits_{i=0}^{\log n}\alpha^i
\end{split}
\end{equation*}
Abgesch\"atzt $M\left( \frac{n}{2}\right) \leq \alpha M(n)$ f\"ur $\alpha < 1$ \\

%%
%% Beginn Vorlesung 13.05.2011

\begin{satz}$\\{}$
Die Division von $2n$-Bit-Zahlen (ganzzahliger Anteil) l"asst sich mit $O(M(n))$ boolschen Operationen durchf"uhren, wobei $M(n)$ die Kosten der
Multiplikation von zwei $n$-Bitzahlen sind und $M(\frac{n}{2}) \leq \alpha M(n)$ f"ur eine Konstante $\alpha \in (0,1)$.
Zum Beispiel in $O(n \cdot \log n \cdot 2^{O(\log^{*}(n))})$
\end{satz}

\section{Berechnung der Quadratwurzel}
geg: nat\"urliche Zahl $a \in \mathbb{N}$
berechne: $\lfloor \sqrt{a} \rfloor$

\subsection{Schulmethode}
\subsubsection{Im Dezimalsystem}
$\US{\text{Bl\"ocke der L\"ange 2 von rechts aus}}{\sqrt{1'23'14}}$

$$
\begin{array}{lllllllllll}
\sqrt{} & 1' &2 &3' &1 &7 &&&&& = 110,9 \cdots \\
\cline{1-4} & 0 &2 &3 &&&&&&&:\US{\text{Ergebnis mal 2}}{2} | \US{\text{Gr\"osste Ziffer x, dass 2x $\cdot$ x $\leq$ 23}}{1} \\
&& 2 & 1 \\
\cline{2-6} &&& 2 & 1 & 7 &&&&&: \US{\text{Ergebnis mal 2}}{22} | \US{\text{Gr\"osste Ziffer x, dass 22x $\cdot$ x $\leq$ 217}}{0} \\
&&&&& 0 \\
\cline{2-8} &&&2 &1 &7 &0 &0 &&& : 220 | 9 \\
&&&1 &9 &8 &8 &1 \\
\cline{2-10} &&&&1 &8 &1 &9 &0 &0 \cdots \\
\end{array}
$$

\subsubsection{Im Bin\"arsystem}

$\US{\text{Bl\"ocke der L\"ange 2 von rechts aus}}{\sqrt{10}}$

$$
\begin{array}{llllllllll}
\sqrt{} &1 &0 &&&&&& = 1,01 \cdots \\
\cline{2-5} &1 & 0& & &&&& \US{\text{Ergebnis mal 2}}{0} | \US{\text{Gr\"osste Ziffer x, dass 0x $\cdot$ x $\leq$ 1}}{1}\\
&&1 & &\\
\cline{2-3} &&1 &0 &0 &&&& \US{\text{Ergebnis mal 2}}{10} | \US{\text{Gr\"osste Ziffer x, dass 10x $\cdot$ x $\leq$ 100}}{0}\\
&&1 &0 &0\\
\cline{2-5} &&1 &0 &0 &0 &0 && 100 | 1\\
&&&1 &0 &0 &1 \\
\cline{2-7} &&&& 1 &1 &1  \cdots
\end{array}
$$

\subsection{Quadratwurzel mit Newton-Iteration berechnen}

$\sqrt{a}$ ist NST von $f(x) = x^2 - a$\\
$x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)} = x_i - \frac{x_i^2 - a}{2x_i} = \US{\text{Erfordert eine Division}}{\frac{1}{2} (x_i + \frac{a}{x_i})}$

Damit:
Quadratwurzel berechnen kostet genau so viel wie die Division (bis auf einen konstanten Faktor)
also auch in $O(n \log n \cdot ^2{\log^{*}n})$ m\"oglich f\"ur n-Bit-Zahlen.

\subsubsection{zum Newtonverfahren}
Angenommen wir haben einen N\"ahrungswert $x_i$, dann liegt $\sqrt{a}$ zwischen $x_i$ und $\frac{a}{x_i}$

%%%% GRAPHIC %%%%

Diese Verfahren stammt von Aeron von Alexandria $\sim 150$ v. Chr.

\section{Primzahltest}
\textbf{gegeben: } eine Zahl $N \in \mathbb{N}$ \\
\textbf{Frage: } Ist $N$ eine Primzahl ? \\
Wir nennen diese Problem \textbf{PRIM}.
\medskip

Standardalgorithmen haben expotentielle Laufzeit in der Bin\"ardarstellung der Zahl, $N$ ist darstellbar mit $n = \lceil \log N \rceil$ Bits.
\begin{itemize}
\item teste f\"ur $2,3, \cdots , N-1$ ob sie $N$ teilen. \\
Dies kostet $\Theta(N \cdot p(n)) = \Theta(2^n \cdot p(n))$
\item teste f\"ur $2,3, \cdots , \sqrt{N}$ ob sie $N$ teilen. \\
Dies kostet $\Theta(\sqrt{N} \cdot p(n)) = \Theta(\sqrt{2n} \cdot p(n)) = \Theta(2^{n/2} \cdot p(n))$
\item \textbf{Sieb des Eratosthenes} $\sim 240$ v. Chr. \\
$
\begin{array}{llllllllllllllll}
\Os{\downarrow}{2} &3 &\not{4} &5 &\not{6} &7 &\not{8} &9 &\not{10} &11 &\not{12} &13 &\not{14} &15 &\not{16} \\
& \Os{\downarrow}{3} & & 5 & & 7 & & \not{9} & & 11 & & 13 & & \not{15} \\
& & & \Os{\downarrow}{5} & & 7 & & & & 11 & & 13 \\
& & & & & \Os{\downarrow}{7} & & & & 11 & & 13 \\
& & & & & & & & & \Os{\downarrow}{11} & & 13 \\
& & & & & & & & & & & \Os{\downarrow}{13} \\
\end{array}
$

Primzahlen sind $2,3,5,7,11,13$.

Die Berechnung aller Primzahlen $\leq N$ kostet ebenso exponentielle Zeit, da schon die Eleminierung der 2-Faktoren exponentielle Zeit ben\"otigt.
\end{itemize}

Es war lange offen und inzwischen gel\"ost:
Ist \textbf{PRIM} $\in$ P? 

\begin{itemize}
\item Leicht zu sehen ist: \\
\textbf{PRIM} $\in$ co-NP, da f\"ur zusammengesetzte Zahlen ist leicht zu pr\"ufen ob sie
zusammengesetzt sind, denn ein Zeuge w\"ar hier ein Teiler. \\
$\sfollow$ zusammengesetzte Zahlen sind in NP \\
$\sfollow$ \textbf{PRIM} $\in$ co-NP

\item \textbf{PRIM} $\in$ NP, gezeigt durch Prat 1975.

\item \textbf{PRIM} $\in$ P, gezeigt 2002 durch Agrawal, Kayal, Saxena. \\
beste bisher bekannte Variante l\"auft in $O(n^{3+\epsilon})$
\end{itemize}

\subsection{Primzahltest von Miller und Rabin}
Der Primzahltest von Miller und Rabin ist eine Montecarlo-Methode, daher zufallsbasiert.
Wenn der Algorithmus bei der Eingabe einer Zahl $N \in \mathbb{N}$ ausgibt die Zahl sei eine Primzahl, dann ist dies immer korrekt.
Wenn er hingegen ausgibt $N$ ist keine Primzahl, dann stimmt dies mit einer Wahrscheinlichkeit von $\frac{1}{2}$. F\"uhrt man den
Algorithmus also $k$ mal aus, hat man mit Wahrscheinlichkeit $2^{-k}$ eine korrekte Antwort.

\medskip
Sei \\
$n \in \mathbb{N}, (\mathbb{Z}_n, \cdot, +)$ Restklassenring mod $n$. \\
$\mathbb{Z}_n^{*} = \{ a \in \mathbb{Z}_n | a \text{ teilerfremd zu } n \}$ \\
$(\mathbb{Z}_n^{*}, \cdot)$ ist multiplikative Gruppe \\
$\left| \mathbb{Z}_n^{*} \right| = \varphi(n)$ Eulerische $\varphi$-Funktion, daher die Anzahl der teilerfremden Zahlen zu n in $\mathbb{Z}_n$.
\medskip

\textbf{Beispiel} \\
$\mathbb{Z}_8^{*} = {1,3,5,7} \leftarrow \varphi(8) = 4$ \\
$\mathbb{Z}_7^{*} = {1,2,3,4,5,6} \leftarrow \varphi(7) = 6$
\medskip

allgemein: $\mathbb{Z}_n^{*} = \{1, \cdots, n-1\} \iff p$ prim, $\varphi(n) = n - 1$

\subsubsection{Kleiner Satz von Fermat}
\begin{satz}
$a^{\varphi(n)} \equiv 1 \text{ mod } n \quad \forall a \in \mathbb{Z}_n^{*}$. \\
Also wenn $n$ Primzahl:
$a^{n-1} \equiv 1 \text{ mod } n \quad \forall a \in \mathbb{Z}_n \setminus \{0\}$
\end{satz}

\subsubsection{Algorithmus (von Miller, Rabin)}
\begin{algorithm}
\caption{PrimMillerRabin($N$,$k$)}
\begin{algorithmic}[1]
\IF{$N$ gerade}
	\IF{$N=2$}
		\STATE antworte "ja"
	\ELSE
		\STATE antworte "nein"
	\ENDIF
\ELSE
	\FOR{$i = 1 \to k$}
		\STATE w\"ahle zuf\"allig und gleichverteilt ein $a \in \mathbb{Z}_N^{*}$
		\IF{$a^{N-1} \not\equiv 1 $ mod $N$}
			\STATE antworte "nein"
		\ELSE
			\STATE bestimme $s$, $t$ mit $N-1 = s \cdot t$ und $s$ ungerade, $t = 2^q$ Zweierpotenz.
			\STATE berechne $a^s, a^{2s}, a^{4s}, \cdots, a^{2^q s}$ mod $N$
			\IF{ein Element der Folge $\not= 1$}
				\STATE w\"ahle letztes das $\not= 1$ und antworte "nein", falls dieses $\not= -1$.
			\ENDIF
		\ENDIF
	\ENDFOR
	\STATE antworte "ja" (also falls alle Tests bestanden)
\ENDIF
\end{algorithmic}
\end{algorithm}

\textbf{Zeile (13)} - Dividiere $N-1$ durch $2$ solange das Ergebnis gerade.\\
Damit ist der Rest $s$ und $(N-1) / s = t$.

\subsubsection{Korrektheit}
Der Algorithmus beruht auf folgender Beobachtung: \\
Falls N Primzahl, so gilt \\
$\forall b \in \mathbb{Z}_n^{*} \setminus \{1,-1\} \quad : b^2 \not\equiv 1 \text{ mod } N$.
\medskip

\begin{proof}
w\"are $b^2 = 1$ (in $\mathbb{Z}_N$) \\
$\sfollow b^2 - 1 = 0 \iff (b - 1)(b + 1) = 0$ \\
da $\mathbb{Z}_n$ K\"orper $\sfollow (b-1) = 0 \lor (b + 1) = 0$ \\
(es existieren in einem Restklassenk\"orper keine Nulleiler)
\end{proof}

\begin{lemma}
Ist $N$ prim, so liefert der MR-Algorithmus die richtige Antwort.
\end{lemma}

\end{document}
